package day190621;

import java.util.HashSet;
import java.util.Stack;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/6/21 下午 03:25
 * 210. 课程表 II
 * https://leetcode-cn.com/problems/course-schedule-ii/
 */
public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }
        if (prerequisites.length == 0) {
            // 没有有向边，则表示不存在课程依赖，任务一定可以完成
            int[] result = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        int[] result = new int[numCourses];
        int[] visit = new int[numCourses];
        HashSet<Integer>[] graph = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new HashSet<>();
        }
        for (int[] value : prerequisites) {
            graph[value[1]].add(value[0]);
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, graph, visit, stack)) {
                return new int[0];
            }
        }
        // 在遍历的过程中，一直 dfs 都没有遇到已经重复访问的结点，就表示有向图中没有环
        // 所有课程任务可以完成，应该返回 true
        // 下面这个断言一定成立，这是拓扑排序告诉我们的结论
        assert stack.size() == numCourses;
        for (int i = 0; i < numCourses; i++) {
            result[i] = stack.pop();
        }

        return result;
    }

    /**
     * 注意这个 dfs 方法的语义
     *
     * @param i      当前访问的课程结点
     * @param graph
     * @param visit 如果 == 1 表示正在访问中，如果 == 2 表示已经访问完了
     * @return true 表示图中存在环，false 表示访问过了，不用再访问了
     */
    private boolean dfs(int i, HashSet<Integer>[] graph, int[] visit, Stack<Integer> stack) {
        if (visit[i] == 1) {
            return true;
        }
        if (visit[i] == 2) {
            return false;
        }
        visit[i] = 1;
        HashSet<Integer> nodes = graph[i];
        for (Integer node : nodes) {
            if (dfs(node, graph, visit, stack)) {
                return true;
            }
        }
        // i 的所有后继结点都访问完了，都没有存在环，则这个结点就可以被标记为已经访问结束
        // 状态设置为 2
        visit[i] = 2;
        stack.push(i);
        return false;
    }
}
